package 数据结构专栏.A_二叉树专栏;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @DESC 我是一棵小小树，有值有左还有右
 * @Author tzq
 * @Date 2020-04-01 10:25
 **/
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode() {
    }

    public TreeNode(int x) {
        val = x;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    /**
     * 构造测试用的树
     *  3
     * / \
     * 9  20
     *    / \
     *   15  7
     */
    public static TreeNode buildDemoTreeNode() {
        TreeNode root = new TreeNode(3);
        TreeNode t1 = new TreeNode(9);
        TreeNode t2 = new TreeNode(20);
        TreeNode t3 = new TreeNode(15);
        TreeNode t4 = new TreeNode(7);
        root.left = t1;
        root.right = t2;
        t2.left = t3;
        t2.right = t4;
        return root;
    }

    /**
     * 构造对称二叉树
     *
     *     1
     *    / \
     *   2   2
     *  / \ / \
     * 3  4 4  3
     *
     * @return
     */
    public static TreeNode buildSymmetricTreeNode() {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(2);
        TreeNode t4 = new TreeNode(3);
        TreeNode t5 = new TreeNode(4);
        TreeNode t6 = new TreeNode(4);
        TreeNode t7 = new TreeNode(3);
        t1.left = t2;
        t1.right = t3;
        t2.left = t4;
        t2.right = t5;
        t3.left = t6;
        t3.right = t7;
        return t1;
    }


    /**
     * 前序打印二叉树
     * @param root
     * @return
     */
    public static ArrayList<Integer> printFromTopToBottom(TreeNode root) {
        ArrayList<Integer> arrayList = new ArrayList<Integer>();
        if (root==null){
            return arrayList;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();//队列：先入先出
        //将树存入队列中，按要求从上到下，从左到右添加到队列中：根、左子、右子
        queue.offer(root);//根：add()和remove()方法在失败的时候会抛出异常(不推荐)，offer代替
        while (!queue.isEmpty()){
            TreeNode node= queue.poll();//树当前节点更新；poll()返回第一个元素，并在队列中删除
            arrayList.add(node.val);//保存当前节点
            if (node.left!=null){
                queue.offer(node.left);//左
            }
            if (node.right!=null){
                queue.offer(node.right);//右
            }
        }
        return arrayList;
    }

}